(1) Field of the Invention
The present invention relates to the reading and writing of data in a processing system. More particularly the invention provides a low overhead update notification mechanism for concurrent processes accessing data bases.
(2) Description of the Prior Art
A known prior art means utilizes an interrupt method in which submarine combat system processes notify each other of their updates to shared resources by using soft interrupts (versus hardware interrupts). These soft interrupts provide inter process update notification. The typical computing system has the interrupting processes (via kernel services) either set conditional flags or queue the conditions, and either asynchronously or synchronously has the interruptible processes (via the operating system) either check the flag or the queue for any interrupting conditions. When a condition exists the operating system invokes interrupt handlers. The interrupt handlers are procedures provided by the executing programs for activation on interrupts. More specifically, processes generate interrupts for other processes by calling the operating system at least once per interrupt. Each call initiates the operating system accesses and updates interrupt natured data structures in the target process. The operating system then allows the interrupts when an interrupt returns true and the process is either in the execution state or in the ready state. The operating system handles the interrupt by placing a handler frame (a call) on the stack. The state of the art, from interrupt generation to handler invocation, requires processing overhead and incurs response latencies. The delays are due to activities that must run to completion before interrupt conditions are acknowledged, which in turn are due to switching to and from the operating system and processes.
Another prior art means utilizes a synchronization method. In this method submarine combat system processes notify each other of their updates to shared resources by invoking synchronization primitives. These primitives are often termed "P" and "V", or "Signal" and "Wait", or "Lock" and "Unlock." When P and V, and Signal and Wait primitives are used, they are implemented as operating system services that require the process surrender the computer system to the operating system. The client does a P/Wait when it needs the update notification and the writer does a V/Signal when it generates the update notification. Each time a process invokes either a P or a V, it will call the operating system at least once per that invocation. This switching to and from the operating system causes P and V primitives to introduce substantial overhead. In addition, P invocations indiscriminately cause writer(s) and reader(s) to wait serially for the resource. The P primitive may also affect the behavior of a priority based real-time system. On some operating systems, P invocations have a tendency of creating a priority inversion when separate priority queues are not maintained for waiting processes. The absence of priority queues treats all processes as equal activities.
P and V primitives are often based on Lock and Unlock operators. Lock and Unlock operators are often directly based on some computer hardware mechanism. In practice, a successful lock allows a process to access the resource; an unsuccessful lock requires the process to re-invoke the lock operator. Many computer systems make Lock and Unlock operators directly available to processes, i.e., they don't require P and V calls, and operating system intervention. Processing of unsuccessful locks is accomplished by having the process either re-invoke the lock until success, or by having it block and continue at some later time, or by having it perform a default action. The reinvoking of the lock is often called a spin-lock and involves busy waiting and hence wastes precious computer system processor cycles. The blocking process as a strategy usually creates the same effect as the P operation, i.e., it serializes access. Unlike the P primitive, the lock operator doesn't have to result in suspended processing, but often default actions are not available when data must be accessed and processed.
Submarine combat systems can conceptually be characterized as a processing pipeline with the flow being occasionally broken by human operator actions. Two generic processing structures in submarine combat systems are manifest when this conceptual model is applied. The progression from data to information usually has many processes feeding many other processes as multiple processing stages. The data bases shared to pipe data from one stage to another stage usually have one writer to each data base, or some set of records in it, and several readers accessing the data bases. This processing structure represents the first category, and the focus of the invention. The second category is another processing structure where the computer system of a submarine combat system operates on data for, presents information to, and assists the actions of its human operators. Many of these actions often result in a break in the combat system processing pipeline. Often access to data bases is necessary, processes acting on the human operator's behalf may require sole access to either select data bases or sets of data base records. This often requires synchronization with writers in some stage of the processing pipeline. This latter processing scenario requires either the P/V or the Lock/Unlock solutions.